package com.faiz.algorithm;

public class FourPeg {

    public static int fourPeg(int n) {
        int res = 1 << 16;
        if (n == 1) {
            return 1;
        }
        for (int i = 1; i < n; i++) {
            int tmp = 2 * fourPeg(n - i) + (1 << i) - 1;
            if (tmp < res) {
                res = tmp;
            }
        }
        return res;
    }

    public static int fourPegOptimise(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = 1 << 16;
            for (int j = 1; j <= i; j++) {
                int tmp = 2 * dp[i - j] + (1 << j) - 1;
                dp[i] = Math.min(dp[i], tmp);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fourPeg(5));
        System.out.println(fourPegOptimise(5));
    }
}
